#include <iostream>
#include <vector>

using namespace std;

class Solution;

class ListNode {

friend class Solution;
public:
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> vec_listnode;
        ListNode* head=root;
        while(head!=NULL){
            vec_listnode.push_back(head);
            head=head->next;
        }
        vector<ListNode*> res(k,NULL);
        if(vec_listnode.size()<k){
            for(int i=0;i<vec_listnode.size();i++){
                vec_listnode[i]->next=NULL;
                res[i]=vec_listnode[i];
            }
        }else{
            int i=0;
            int part=k;
            int part_len=0;
            int vec_len=vec_listnode.size();
            ListNode* tmp=NULL;
            ListNode* cur=root;
            res[0]=root;
            cout<<"idx:"<<0<<endl;
            while(part>0){
                i=1;
                part_len=vec_len%part==0?vec_len/part:(vec_len/part)+1;
                cout<<"Part "<<part<<",len "<<part_len<<endl;
                vec_len=vec_len-part_len;
                while(i<part_len){
                    cout<<"cur:"<<cur->val<<endl;
                    cur=cur->next;
                    i++;
                }
                cout<<"cur val:"<<cur->val<<endl;
                tmp=cur->next;
                cur->next=NULL;
                cur=tmp;
                res[k-part+1]=tmp;
                cout<<"vec idx:"<<k-part+1<<",part idx:"<<part<<endl;
                part=part-1;
            }
        }
        return res;
        /*
        vector<ListNode*> vec_listnode(k,NULL);
        int len=0;
        ListNode* cur=root;
        while(cur!=NULL){
            len++;
            cur=cur->next;
        }
        //cout<<"len:"<<len<<endl;
        cur=root;
        ListNode* last=NULL;
        int cur_len=0;
        int times=k;
        for(int i=0;i<times;i++){
            vec_listnode[i]=cur;
            cur_len=(len%k==0?len/k:len/k+1);
            k--;
            //cout<<"i:"<<i<<" len:"<<len<<" cur_len:"<<cur_len<<" k:"<<k<<" cur_val:"<<cur->val<<endl;
            len=len-cur_len;
            int j=0;
            while(j<cur_len){
                last=cur;
                cur=cur->next;
                j++;
            }
            if(cur==NULL){
                break;
            }
            //cout<<"cur:"<<cur->val<<" last:"<<last->val<<endl;
            if(last!=NULL){
                last->next=NULL;
            }
        }
        return vec_listnode;
        */
    }
};

int main(){
    ListNode* node7=new ListNode(7);
    ListNode* node6=new ListNode(6);
    node6->next=node7;
    ListNode* node5=new ListNode(5);
    node5->next=node6;
    ListNode* node4=new ListNode(4);
    node4->next=node5;
    ListNode* node3=new ListNode(3);
    node3->next=node4;
    ListNode* node2=new ListNode(2);
    node2->next=node3;
    ListNode* node1=new ListNode(1);
    node1->next=node2;
    Solution s;
    vector<ListNode*> res=s.splitListToParts(node1,3);
    cout<<"res size:"<<res.size()<<endl;
    return 0;
}


/*
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> vec_listnode;
        ListNode* head=root;
        while(head!=NULL){
            vec_listnode.push_back(head);
            head=head->next;
        }
        vector<ListNode*> res(k,NULL);
        if(vec_listnode.size()<k){
            for(int i=0;i<vec_listnode.size();i++){
                vec_listnode[i]->next=NULL;
                res[i]=vec_listnode[i];
            }
        }else{
            int i=0;
            int part=k;
            int part_len=0;
            int vec_len=vec_listnode.size();
            ListNode* tmp=NULL;
            ListNode* cur=root;
            res[0]=root;
            //cout<<"idx:"<<0<<endl;
            while(part>1){
                i=1;
                part_len=vec_len%part==0?vec_len/part:(vec_len/part)+1;
                //cout<<"Part "<<part<<",len "<<part_len<<endl;
                vec_len=vec_len-part_len;
                while(i<part_len){
                    //cout<<"cur:"<<cur->val<<endl;
                    cur=cur->next;
                    i++;
                }
                //cout<<"cur val:"<<cur->val<<endl;
                tmp=cur->next;
                cur->next=NULL;
                cur=tmp;
                res[k-part+1]=tmp;
                //cout<<"vec idx:"<<k-part+1<<",part idx:"<<part<<endl;
                part=part-1;
            }
        }
        return res;
    }
};